// Copyright (c) 2010, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// ---
// Author: Jeffrey Junfeng Pan (panjunfeng@gmail.com)

// class Itemsets is used for storing the results of frequent pattern mining.
// A result may have multiple itemsets and their frequencies. These itemsets
// can be sorted by itemset size and frequency.

#ifndef FP_GROWTH_ITEMSETS_H_
#define FP_GROWTH_ITEMSETS_H_

#include <algorithm>
#include <deque>
#include <unordered_map>
#include <sstream>
#include <string>
#include <vector>

#include "base.h"
#include "common/scoped_ptr.h"
#include "common/strutil.h"
#include "transactions.h"

namespace frequent_pattern_mining {

// ------------------------------------------------------------
//                      Declaration
// ------------------------------------------------------------

template <typename T>
class Itemsets {
 public:
  typedef deque<ItemsetFrequencyPair<T> > ItemsetFrequencyPairVector;
  // Constructor
  Itemsets();

  // Destructor
  ~Itemsets();

  // Insert an itemset into the itemset repository with a given frequency
  void InsertItemset(const ItemsetFrequencyPair<T>& itemset);

  // Insert an itemset into the itemset repository with default frequency 1
  void InsertItemset(const vector<T>& itemset);

  // Sort all itemsets by itemset size ascendingly as the first key
  // and itemset frequency descendingly as the second key.
  void SortByItemsetSizeFrequency();

  // Sort all itemsets by itemset frequency descendingly as the first key
  // and itemset size ascendingly as the second key.
  void SortByItemsetFrequencySize();

  // Sort all itemsets by itemset frequency descendingly as the first key
  // and itemset size ascendingly as the second key.
  void SortByItemsetFrequencyReverseSize();

  // Convert the whole itemsets into a string.
  string ToString() const;

  // Retrieve the actual itemsets
  const ItemsetFrequencyPairVector& itemsets() const;

  // Get the number of transactions in the original dataset
  int num_transactions() const;

  // Get the number of transactions that are covered by the major patterns.
  int num_covered_transactions() const;

  // Set the number of transactions that are covered by the major patterns.
  void set_num_covered_transactions(int num_covered_transactions);

  // Set the number of transactions from which the patterns are extracted.
  void set_num_transactions(int num_transactions);

  static bool Contains(const vector<T>& itemset1,
                       const vector<T>& itemset2);

  static bool Overlaps(const vector<T>& itemset1,
                       const vector<T>& itemset2);

  static bool Equals(const vector<T>& itemset1,
                     const vector<T>& itemset2);

  // Analyze itemset structure:
  //   1) Whether an itemset is a direct parent of another. If Itemset A is
  //      a subset of Itemset B and B has only one more item than A, we say
  //      B is a direct parent of A.
  //   2) Whether an itemset is partial. If an itemset A has a parent
  //      itemset B, both having the same frequency, we say A is partial.
  //      A word in a phrase is usually partial. For example, both "New"
  //      and "York" may be partial itemsets of their parent "New York".
  void AnalyzeItemsetStructure();

 private:

  // Refresh the internal index of all itemsets and the parents.
  void RefreshInternalIndexAfterSorting();

  // the itemsets.
  scoped_ptr<ItemsetFrequencyPairVector > itemsets_;

  // number of transactions in the original dataset.
  int num_transactions_;

  // number of transactions are covered by the selected patterns.
  // the value is only useful after running the pattern selection algorithm.
  int num_covered_transactions_;

  // Has call AnalyzeItemsetStructure() and data are up-to-date
  bool analysis_done_;

  DISALLOW_EVIL_CONSTRUCTORS(Itemsets);
};

// ------------------------------------------------------------
//                      Definition
// ------------------------------------------------------------

// Comparison function for sorting all itemsets by itemset size ascendingly
// as the first key and itemset frequency descendingly as the second key.
template <typename T>
class ItemsetFrequencyPairCompareBySizeFrequency {
 public:
  int operator() (const ItemsetFrequencyPair<T>& left,
                  const ItemsetFrequencyPair<T>& right) {
    return ((left.itemset.size() < right.itemset.size()) ||
            ((left.itemset.size() == right.itemset.size()) &&
            (left.frequency > right.frequency)));
  }
};

// Comparison function for sorting all itemsets by itemset frequency
// descendingly as the first key and itemset size ascendingly as the second key.
template <typename T>
class ItemsetFrequencyPairCompareByFrequencySize {
 public:
  int operator() (const ItemsetFrequencyPair<T>& left,
                  const ItemsetFrequencyPair<T>& right) {
    return ((left.frequency > right.frequency) ||
            ((left.frequency == right.frequency) &&
            (left.itemset.size() < right.itemset.size())));
  }
};

// Comparison function for sorting all itemsets by itemset frequency
// descendingly as the first key and itemset size ascendingly as the second key.
template <typename T>
class ItemsetFrequencyPairCompareByFrequencyReverseSize {
 public:
  int operator() (const ItemsetFrequencyPair<T>& left,
                  const ItemsetFrequencyPair<T>& right) {
    return ((left.frequency > right.frequency) ||
            ((left.frequency == right.frequency) &&
            (left.itemset.size() > right.itemset.size())));
  }
};

// Constructor
template <typename T>
Itemsets<T>::Itemsets()
  : itemsets_(new ItemsetFrequencyPairVector),
    num_transactions_(0),
    num_covered_transactions_(0),
    analysis_done_(false) {
}

// Destructor
template <typename T>
Itemsets<T>::~Itemsets() {
}


// Insert an itemset into the itemset repoisitory with a given frequency
template <typename T>
void Itemsets<T>::InsertItemset(
    const ItemsetFrequencyPair<T>& itemset) {
  itemsets_->push_back(itemset);
  int index = itemsets_->size() - 1;
  (*itemsets_)[index].index = index;
  analysis_done_ = false;
}

// Insert an itemset into the itemset repository with default frequency 1
template <typename T>
void Itemsets<T>::InsertItemset(
    const vector<T>& itemset) {
  ItemsetFrequencyPair<T> value;
  value.itemset = itemset;
  value.frequency = 1;
  itemsets_->push_back(value);
  int index = itemsets_->size() - 1;
  (*itemsets_)[index].index = index;
  analysis_done_ = false;
}

// Retrieve the actual itemsets
template <typename T>
const typename Itemsets<T>::ItemsetFrequencyPairVector&
  Itemsets<T>::itemsets() const {
  return *(itemsets_.get());
}

// Refresh the internal index of all itemsets and the parents
template <typename T>
void Itemsets<T>::RefreshInternalIndexAfterSorting() {
  vector<int> indices;
  indices.resize(itemsets_->size());
  for (int i = 0; i < itemsets_->size(); ++i) {
    // store the old index to new index mapping
    indices[(*itemsets_)[i].index] = i;
    (*itemsets_)[i].index = i;
  }
  for (int i = 0; i < itemsets_->size(); ++i) {
    for (int j = 0; j < (*itemsets_)[i].parents.size(); ++j) {
      (*itemsets_)[i].parents[j] = indices[(*itemsets_)[i].parents[j]];
    }
  }
}

// Sort all itemsets by itemset size ascendingly as the first key
// and itemset frequency descendingly as the second key.
template <typename T>
void Itemsets<T>::SortByItemsetSizeFrequency() {
  sort(itemsets_->begin(),
       itemsets_->end(),
       ItemsetFrequencyPairCompareBySizeFrequency<T>());
  RefreshInternalIndexAfterSorting();
}

// Sort all itemsets by itemset frequency descendingly as the first key
// and itemset size ascendingly as the second key.
template <typename T>
void Itemsets<T>::SortByItemsetFrequencySize() {
  sort(itemsets_->begin(),
       itemsets_->end(),
       ItemsetFrequencyPairCompareByFrequencySize<T>());
  RefreshInternalIndexAfterSorting();
}

// Sort all itemsets by itemset frequency descendingly as the first key
// and itemset size ascendingly as the second key.
template <typename T>
void Itemsets<T>::SortByItemsetFrequencyReverseSize() {
  sort(itemsets_->begin(),
       itemsets_->end(),
       ItemsetFrequencyPairCompareByFrequencyReverseSize<T>());
  RefreshInternalIndexAfterSorting();
}

template <typename T>
int Itemsets<T>::num_transactions() const {
  return num_transactions_;
}

template <typename T>
void Itemsets<T>::set_num_transactions(
    int num_transactions) {
  CHECK_GE(num_transactions, 0)
    << ": the number of transactions must be non negative";
  num_transactions_ = num_transactions;
}

// Convert the whole itemsets into a string.
template <typename T>
string Itemsets<T>::ToString() const {
  ostringstream oss;
  for (int i = 0; i < itemsets_->size(); ++i) {
    // Generate Prefix, indicating internal labels of itemsets
    string prefix;
    prefix += (*itemsets_)[i].is_partial ? "x" : " ";
    prefix += (*itemsets_)[i].is_phrase ? "o" : " ";
    float percent = (num_transactions_ == 0) ? 0.0 :
        static_cast<float>((*itemsets_)[i].frequency) /
        static_cast<float>(num_transactions_) * 100.0;

    // Combine all items into a space-separated-value string
    string items;
    for (int j = 0; j < (*itemsets_)[i].itemset.size(); ++j) {
      items += ItemToString((*itemsets_)[i].itemset[j]);
      items += (j < (*itemsets_)[i].itemset.size() - 1) ? " " : "";
    }

    // Combine all parent indices into a space-separated-value string
    string parents;
    for (int j = 0; j < (*itemsets_)[i].parents.size(); ++j) {
      parents += SimpleItoa((*itemsets_)[i].parents[j]);
      parents += (j < (*itemsets_)[i].parents.size() - 1) ? " " : "";
    }

    // Combine all children indices into a space-separated-value string
    string children;
    for (int j = 0; j < (*itemsets_)[i].children.size(); ++j) {
      children += SimpleItoa((*itemsets_)[i].children[j]);
      children += (j < (*itemsets_)[i].children.size() - 1) ? " " : "";
    }

    // Show the itemset and its related information.
    oss << StringPrintf(
             "%sINDEX %3d, FREQUENCY %3d : %5.1f%%, "
             "PARENTS[%20s], CHILDREN[%20s], ITEMS %s\n",
             prefix.c_str(),
             (*itemsets_)[i].index,
             (*itemsets_)[i].frequency,
             percent,
             parents.c_str(),
             children.c_str(),
             items.c_str());
  }  // for i
  return oss.str();
}

// Get the number of transactions that are covered by the selected patterns.
template <typename T>
int Itemsets<T>::num_covered_transactions() const {
  return num_covered_transactions_;
}

// Set the number of transactions that are covered by the selected patterns.
template <typename T>
void Itemsets<T>::set_num_covered_transactions(int num_covered_transactions) {
  CHECK_GE(num_covered_transactions, 0) << ": value must be non-negative.";
  num_covered_transactions_ = num_covered_transactions;
}


// Check if the elements in itemset2 are included in itemset1.
template <typename T>
inline bool Itemsets<T>::Contains(const vector<T>& itemset1,
                                  const vector<T>& itemset2) {
  // itemset is the terms in a keyword. a keyword usually has 3 or 5 terms
  // only. The complexity is O(n*m) where n and m are the size of itemset1 and
  // itemset2 respectively. Since n and m are small, it maybe ok. If n or m is
  // large, consider using hash_map instead.
  for (int i = 0; i < itemset2.size(); ++i) {
    if (find(itemset1.begin(), itemset1.end(), itemset2[i]) == itemset1.end()) {
      return false;
    }
  }
  return true;
}

// Check if the elements in itemset1 and itemset2 are overlapping.
template <typename T>
inline bool Itemsets<T>::Overlaps(const vector<T>& itemset1,
                                  const vector<T>& itemset2) {
  // itemset is the terms in a keyword. a keyword usually has 3 or 5 terms
  // only. The complexity is O(n*m) where n and m are the size of itemset1 and
  // itemset2 respectively. Since n and m are small, it maybe ok. If n or m is
  // large, consider using hash_map instead.
  for (int i = 0; i < itemset2.size(); ++i) {
    if (find(itemset1.begin(), itemset1.end(), itemset2[i]) != itemset1.end()) {
      return true;
    }
  }
  return false;
}

// Check if the elements in itemset2 and itemset1 are identical.
template <typename T>
inline bool Itemsets<T>::Equals(const vector<T>& itemset1,
                                const vector<T>& itemset2) {
  // itemset is the terms in a keyword. a keyword usually has 3 or 5 terms
  // only. The complexity is O(n*m) where n and m are the size of itemset1 and
  // itemset2 respectively. Since n and m are small, it maybe ok. If n or m is
  // large, consider using hash_map instead.
  if (itemset1.size() != itemset2.size()) {
    return false;
  } else {
    return Contains(itemset1, itemset2);
  }
}

// Analyze itemset structure:
//   1) Whether an itemset is a direct parent of another. If Itemset A is
//      a subset of Itemset B and B has only one more item than A, we say
//      B is a direct parent of A.
//   2) Whether an itemset is partial. If an itemset A has a parent
//      itemset B, both having the same frequency, we say A is partial.
//      A word in a phrase is usually partial. For example, both "New"
//      and "York" may be partial itemsets of their parent "New York".
template <typename T>
void Itemsets<T>::AnalyzeItemsetStructure() {
  if (!analysis_done_) {
    SortByItemsetSizeFrequency();
    for (int i = 0; i < itemsets_->size(); ++i) {
      (*itemsets_)[i].parents.clear();
      int i_size = (*itemsets_)[i].itemset.size();
      for (int j = i + 1; j < itemsets_->size(); ++j) {
        int j_size = (*itemsets_)[j].itemset.size();
        CHECK_GE(j_size, i_size) << ": Itemsets are not properly ordered.";
        if (j_size == i_size) continue;
        if (j_size > i_size + 1) break;
        if (Contains((*itemsets_)[j].itemset, (*itemsets_)[i].itemset)) {
          (*itemsets_)[i].parents.push_back(j);
          (*itemsets_)[j].children.push_back(i);
          // if ((*itemsets_)[j].frequency == (*itemsets_)[i].frequency) {
          //  (*itemsets_)[i].is_partial = true;
          // }
        }
      }  // for j
    }  // for i

    // Find phrase in itemset lattice. Assume the itemsets are sorted
    // ascendingly for itemset size as the key.
    // int last_size = 1;
    // int last_index = 0;
    vector<int> reset;
    for (int i = 0; i < itemsets_->size(); ++i) {
      // If the itemset is a leaf node (single item), set is_phrase = true.
      // Otherwise, check the frequency and make sure it is a phrase.
      if ((*itemsets_)[i].itemset.size() == 1) {
        (*itemsets_)[i].is_phrase = true;
      } else {
        bool is_phrase = true;
        for (int j = 0; j < (*itemsets_)[i].children.size(); ++j) {
          if (!(*itemsets_)[(*itemsets_)[i].children[j]].is_phrase ||
              (*itemsets_)[(*itemsets_)[i].children[j]].frequency !=
              (*itemsets_)[i].frequency) {
            is_phrase = false;
            break;
          }
        }  // for j (all children of current itemset)
        (*itemsets_)[i].is_phrase = is_phrase;
        if (is_phrase) {
          for (int j = 0; j < (*itemsets_)[i].children.size(); ++j) {
            reset.push_back((*itemsets_)[i].children[j]);
            // TODO(panjf) there is duplicated itemsets stored reset, though
            // not hurt.
          }
        }
      }  // if itemset.size

      /*
      // We scan to a upper level of the itemset lattice or not ?
      if ((*itemsets_)[i].itemset.size() != last_size ||
          i + 1 == itemsets_->size()) {
        cout << "scan " << last_index << " " << i << endl;
        // Check all itemsets with index in [last_index, i - 1].
        // If it is a phrase, its children shall not be phrase.
        for (int j = last_index; j < i; ++j) {
          // If the current itemset is_phrase = true,
          // set all of its children itemsets is_phrase = false
          if ((*itemsets_)[j].is_phrase) {
            for (int k = 0; k < (*itemsets_)[j].children.size(); ++k) {
              (*itemsets_)[(*itemsets_)[j].children[k]].is_phrase = false;
            }
          }  // if is_phrase
        }  // for all itemsets with this level.
        last_index = i;
        last_size = (*itemsets_)[i].itemset.size();
      }  // if we move to an upper level of the itemset lattice.
      */

    }  // for i (all itemsets)
    for (int i = 0; i < reset.size(); ++i) {
      (*itemsets_)[reset[i]].is_phrase = false;
      (*itemsets_)[reset[i]].is_partial = true;
    }

    analysis_done_ = true;
  }  // if analysis is not yet done.
}


}  // namespace frequent_pattern_mining

#endif  // FP_GROWTH_ITEMSETS_H_
